The present invention relates to apparatus and methods for facilitating routing protocol in a computer network. More specifically, it relates to flooding Link State Packets or Packet Data Units (LSP's), which are used in a link state type protocol, such as the IS-IS protocol.
In a network that uses the IS-IS protocol, for example, each node generates a set of LSP's that describe its connectivity to its neighbors and floods these LSP's to its neighbors at appropriate times as specified by the protocol or customized programming. This connectivity information specifies who is connected to whom and the cost associated with each connection, such as a value that is configured by an operator to correspond to a speed of a particular connection. Thus, each node receives connectivity information in the form of LSP's from its neighbors. The LSP's received at a particular node are then flooded by the particular node to its neighbors and, hence, propagated throughout the network. Each node in the network then uses its received LSP's to build a map of connectivity (sometimes referred to as a “shortest path tree” or SPT) using an algorithm, such as “shortest path first” or SPF) and determine possible routing paths (e.g., to form a routing table) based on the map of connectivity.
In some IS-IS implementations, the LSP's are organized by an 8 octet field (i.e., system ID+pseudonode ID+fragmentation number) in ascending order. When the LSP's are flooded, the LSP's with the smallest IDs are likely sent first because of their order in the LSP database. In the example of FIG. 1A, Node A (108) sends LSP's to its new IS-IS neighbor Node B (110). The LSP's includes Node A's LSP, Node X's LSP, Node Y's LSP, and Node Z's LSP. In this example network, Node X (102) is several hops away from node A. That is, Node Y (104) and Node Z (106) are positioned between Nodes X and A. When the LSP for Node X has the smallest system ID, Node B will receive the LSP for Node X first from Node A. Unfortunately, Node B may not be able to compute an SPT (shortest path tree) using an SPF (shortest path first) algorithm to node X because Node B has not yet received and processed LSP's from node A or any other nodes that have higher system ID values, such as Nodes Y or Z.
In another IS-IS implementation, the LSP's may be flooded based on the same 8 octets structure, but in descending order. In doing so, this may also result in prolonging node B's ability to reach node X if node X has the largest system ID. An IS-IS implementation may also choose to flood the LSP's in no particular order. By chance, the LSP for node X may still arrive ahead of other LSP's in the path to node X. Again, Node B will be delayed in converging on a path to node X.
In sum if the newly established router receives only the LSP's from the far away nodes and then computes an SPT, it may not discover a path to any nodes until it has received all the LSP's due to the failure of the two way connectivity check. This problem can be best described in the following simplified scenario that is also illustrated by the networks 150 and 152 of FIG. 1B. Network_1 (150) and Network_2 (152) are merged by connecting Node A (160) that belongs to Network_1 and Node E (164) that belong to Network_2. The nodes A and E are connected via an interface 162. Node A will flood all its LSP's for Network_1 to Node E, which will in turn flood these LSP's to all of the nodes of Network_2. Node A's own LSP will be flooded last. A particular node in Network_2 will receive LSP's of many nodes of Network_1, which will trigger calculation of an SPT. But each time that the particular node calculates the SPT to reach nodes in Network_1, it does not discover any paths because it has not received the LSP's of Node A that will arrive last.
In view of the above, there is a need for improved mechanisms for flooding LSP's in an efficient manner so that useful connectivity maps (or SPT's) may be determined efficiently.